package tianhao.luo.tree;

import java.util.Arrays;

/**
 * 堆排序
 * @author: tianhao.luo@hand-china.com 2021/6/24  下午9:40
 */
public class HeapSort {

    private int[] array;

    public HeapSort(int[] array) {
        this.array = array;
    }

    /**
     * 堆排序
     */
    public void sort(){
        // 将无序序列构建成一个堆,根据升序降序需求来选择大顶堆或小顶堆
        // array.length/2 -1表示非叶子结点的最底一层开始元素索引
        for (int i = array.length/2 -1; i >= 0 ; i--) {
            adjustHeap(i,array.length);
        }

        int temp;
        // 将堆顶元素与末尾元素交换,将最大元素沉到数组末端
        // 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序
        for (int i = array.length-1; i >0; i--) {
            // 交换
            temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            adjustHeap(0,i);
        }
//        System.out.println(Arrays.toString(array));
    }


    /**
     * 将一个数组(二叉树),调整为一个大顶堆
     * 完成将以i对应的非叶子节点的树,调整成大顶堆
     * 举例:{4,6,8,5,9}=> i=1 =>得到{4,9,8,5,6}
     * 如果我们再次调用,传入i=0=>的到{9,6,8,5,4}
     * @param i 表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素进行调整,length在逐渐减少
     */
    public void adjustHeap(int i,int length){

        // 先取出当前元素的值,保存在临时变量
        int temp = array[i];
        // 开始调整
        // 说明
        // 1. k=i*2+1, k是i结点的左子节点
        for (int k = i*2+1; k < length; k=k*2+1) {
            // 左子节点的值小于右子节点的值
            if (k+1<length && array[k]<array[k+1]){
                // 指向右子节点
                k++;
            }
            // 如果子节点大于父节点
            if (array[k] > temp){
                // 把较大的的值赋给当前结点
                array[i] = array[k];
                // i指向k,继续循环比较
                i =k;
            }else {
                break;
            }
            // 当for循环结束后,我们已经将以i为父节点的树的最大值,放在了最顶上

            // 将temp放到调整后的位置
            array[i] = temp;

        }
    }
}
